With the proliferation of small and medium sized personal computers located at a number of physically separated sites and used by a number of different users, there is also an accompanying need and desire to interface the individual computer sites into a large network in order to facilitate communications between and amongst each network site. As the number of sites in a network grows and the physical separation distance between networked sites grows, it is important to provide a network which will enable communication at a relatively high rate of speed in order to accommodate a large number of computers interconnected in on network.
One such large network is a token ring network. In a token ring configuration, a number of local sites are serially connected by a transmission medium to form a closed loop. Information is then transmitted sequentially, as a stream of data called a message, from one active station to the next. Each station generally regenerates and repeats each message and serves as the means for attaching one or more devices to the ring for the purpose of communicating with other devices on the ring. A given site that has access to the transmission medium transmits information onto the ring, where the information then circulates from one station to the next. The information is accompanied by an address which designates the destination sites and copies the information as it passes. The message travels around the serially interconnected stations and is finally returned to the initial source site which then removes the transmitted information from the ring.
A site gains the right to transmit its information onto the medium when it detects and captures a token passing on the medium. The token is a control signal comprised of a unique symbol sequence that circulates on the medium in addition to transmitted data. After the detection of a token, the site detecting the token may remove the token from the ring. That site may then transmit one or more flames of information, and at the completion of its data transmission, issues a new token which provides other sites the opportunity to gain access to the ring. The length of time in which a site may occupy the medium before passing the token is controlled by a token-holding timer.
In addition to ring access being arbitrated by a token, multiple levels of priority are available for independent and dynamic assignment of ring bandwidth, depending upon the relative class of service required. The classes of service are synchronous, asynchronous, or immediate service. For all classes of service, the allocation of a finite ring bandwidth occurs by mutual agreement among the users of the ring. The finite bandwidth is primarily divided into the formentioned classes as defined above into synchronous and asynchronous portions. Asynchronous communication defines a class of data transmission service in which all requests for service contend for a pool of dynamically allocated ring bandwidth and response time. Synchronous communication defines a class of data transmission service in which each requester is preallocated a maximum bandwidth and guaranteed a response time not to exceed a specific delay. Immediate data transmission is generally used only for extraordinary applications such as ring recovery.
When a number of network sites are distributed over distance of several miles, the transmission medium over which that data is transmitted becomes of much greater importance. One such transmission medium over which a number of network stations may be interconnected is a fiber optic medium. In a fiber optic medium, optical signals from light-generating transmitters are propagated through optical fiber wave-guides to light-detecting receivers. The above named classes of data transmission are implemented in a standardized fiber optic network defined as a fiber distributed data interface (FDDI). The FDDI generally consists of a number layers: a physical layer, which defines the physical requirements of the data interface; a data layer, which defines fair and deterministic access to the medium as well as a common protocol to ensure data integrity; and a station management layer, which defines the control necessary at the station level to manage the processes underway in the various FDDI layers. It is important that how applications use the services provided by the FDDI to support real-time communications. More specifically, it is important to provide a system of calculating the synchronous bandwidth allocation needed at a station to guarantee that each real-time message be transmitted within a requested delay bound.
Note that an FDDI token ring network provides a guaranteed throughput for synchronous messages and a bounded medium access delay for each node/station. However, this fact alone cannot effectively support many real-time applications that require the timely delivery of each and every critical message. The reason for this is that the FDDI guarantees a medium access delay bound to nodes, but not to messages. The message-delivery delays may exceed the medium-access delay bound even if messages are generated at a rate not larger than the guaranteed throughput.
For further background, the following is a list of articles describing prior techniques useful in token passing systems.
G. Agrawal, B. Chen, W. Zhao, and S. Davari. Guaranteeing synchronous message deadlines with the timed token protocol. In Proceedings of IEEE International Conference on Distributed Computing Systems. IEEE, June 1992; B. Chen, G. Agrawal, and W. Zhao. Optimal synchronous capacity allocation for hard real-time communications with the timed token protocol. In Proceedings of Real-Time Systems Symposium. IEEE, December 1992; FDDI Station Management (SMT)--draft proposed. American National Standard, ANSI X3T9/92-067, Jun. 25, 1992; Fiber Distributed Data Interface (FDDI)--Token Ring Media Access Control (MAC). American National Standard, ANSI X3.139, 1987; Domenico Ferrari and Dinesh C. Verma. A scheme for real-time channel establishment in wide-area networks. IEEE Journal on Selected Areas in Communications SAC-8(3):368-379, April 1990; Dilip D. Kandlur, Kang G. Shin, and Domenico Ferrari. Real-time communication in multi-hop networks. In Proceedings of 11th conference on Distributed Computer Systems, pages 300-307. IEEE, May 1991; Floyd E. Ross. An overview of FDDI: The fiber distributed data interface. IEEE Journal on Selected Areas in Communications, 7(7):1043-1051, September 1989; K. C. Sevcik and M. J. Johnson. Cycle time properties of the FDDI token ting protocol. Technical Report CSRI-179, Computer Science Research Institute, University of Toronto, 1986; K. G. Shin and Qin Zheng. FDDI-M: a scheme to double FDDI's ability of supporting synchronous traffic. Patent pending; Alfred C. Weaver. Local area networks and busses--an analysis. Technical report, Flight Data Systems, NASA-Johnson Space Center, 1986; Qin zheng. Real-time Fault-tolerant Communication in Computer Networks. PhD thesis, University of Michigan, 1993; Qin Zheng and Kang G. Shin. Fault-tolerant real-time communication in distributed computing systems. In Proc. 22nd Annual International Symposium on Fault-tolerant Computing, pages 86-93, 1992; Qin Zheng and Kang G. Shin. Real-time communication in local area ring networks. In Proceedings of Conference on Local Computer Networks, pages 416-425, September 1992; Qin Zheng and Kang G. Shin. On the ability of establishing real-time channels in point-to-point packet-switched networks. IEEE Transactions on Communication (in press), 1993; Qin Zheng, Kang G. Shin, and Abram-Profeta. Transmission of compressed digital motion video over computer networks. In Digest of COMPCON Spring'93, pages 37-46, February 1993;